<!DOCTYPE html>
<html lang="zh-cn" itemscope itemtype="http://schema.org/WebPage">
<head>
  <meta charset="utf-8">
  <meta http-equiv="X-UA-Compatible" content="IE=edge">
  <title>友知弄</title>
  

<meta name="renderer" content="webkit" />
<meta name="viewport" content="width=device-width, initial-scale=1, maximum-scale=1"/>

<meta name="MobileOptimized" content="width"/>
<meta name="HandheldFriendly" content="true"/>


<meta name="applicable-device" content="pc,mobile">

<meta name="theme-color" content="#f8f5ec" />
<meta name="msapplication-navbutton-color" content="#f8f5ec">
<meta name="apple-mobile-web-app-capable" content="yes">
<meta name="apple-mobile-web-app-status-bar-style" content="#f8f5ec">

<meta name="mobile-web-app-capable" content="yes">

<meta name="author" content="yixy" />
  <meta name="description" content="YOUZHILANE" />
  <meta name="keywords" content="essay, notes" />






<meta name="generator" content="Hugo 0.56.1" />


<link rel="canonical" href="https://yixy.github.io/youzhilane/" />
<link href="%7balternate%20%7bRSS%20application/rss&#43;xml%20%20index%20alternate%20%20false%20false%20true%20false%20false%200%7d%20/youzhilane/index.xml%20https://yixy.github.io/youzhilane/index.xml%7d" rel="alternate" type="application/rss+xml" title="友知弄" />



<link rel="icon" href="/youzhilane/favicon.ico" />











<link rel="stylesheet" href="/youzhilane/sass/jane.min.af20b78e95c84de86b00a0242a4a77bd2601700e1b250edf27537d957ac0041d.css" integrity="sha256-ryC3jpXITehrAKAkKkp3vSYBcA4bJQ7fJ1N9lXrABB0=" media="screen" crossorigin="anonymous">





<meta property="og:title" content="友知弄" />
<meta property="og:description" content="YOUZHILANE" />
<meta property="og:type" content="website" />
<meta property="og:url" content="https://yixy.github.io/youzhilane/" />

<meta property="og:updated_time" content="2019-11-17T00:22:22+08:00" />
<meta itemprop="name" content="友知弄">
<meta itemprop="description" content="YOUZHILANE">

<meta name="twitter:card" content="summary"/>
<meta name="twitter:title" content="友知弄"/>
<meta name="twitter:description" content="YOUZHILANE"/>

<!--[if lte IE 9]>
  <script src="https://cdnjs.cloudflare.com/ajax/libs/classlist/1.1.20170427/classList.min.js"></script>
<![endif]-->

<!--[if lt IE 9]>
  <script src="https://cdn.jsdelivr.net/npm/html5shiv@3.7.3/dist/html5shiv.min.js"></script>
  <script src="https://cdn.jsdelivr.net/npm/respond.js@1.4.2/dest/respond.min.js"></script>
<![endif]-->




</head>
<body>
  <div id="mobile-navbar" class="mobile-navbar">
  <div class="mobile-header-logo">
    <a href="/youzhilane/" class="logo">友知弄</a>
  </div>
  <div class="mobile-navbar-icon">
    <span></span>
    <span></span>
    <span></span>
  </div>
</div>
<nav id="mobile-menu" class="mobile-menu slideout-menu">
  <ul class="mobile-menu-list">
    <li class="mobile-menu-item">
        
          
          
            <a class="menu-item-link" href="https://yixy.github.io/youzhilane/">主页</a>
          
        
      </li><li class="mobile-menu-item">
        
          
          
            <a class="menu-item-link" href="https://yixy.github.io/youzhilane/categories/">分类</a>
          
        
      </li><li class="mobile-menu-item">
        
          
          
            <a class="menu-item-link" href="https://yixy.github.io/youzhilane/booklist/">书单</a>
          
        
      </li><li class="mobile-menu-item">
        
          
          
            <a class="menu-item-link" href="https://yixy.github.io/youzhilane/about/">关于友知弄</a>
          
        
      </li><li class="mobile-menu-item">
        
          
          
            <a class="menu-item-link" href="https://github.com/yixy" rel="noopener" target="_blank">
              GitHub
              
              <i class="iconfont">
                <svg class="icon" viewBox="0 0 1024 1024" version="1.1"
  xmlns="http://www.w3.org/2000/svg" xmlns:xlink="http://www.w3.org/1999/xlink"
  width="18" height="18">
  <path d="M623.36 272.96 473.216 423.04C467.2 429.056 467.072 438.656 472.896 444.416c0 0-6.72-6.656 1.6 1.6C496.064 467.648 528.64 500.224 528.64 500.224 534.464 506.048 544 505.856 550.016 499.904l150.08-150.144 67.328 66.432c9.024 8.96 27.456 4.544 30.4-8.96 19.968-92.608 46.656-227.52 46.656-227.52 6.848-34.496-16.192-56.704-49.92-49.92 0 0-134.656 26.816-227.328 46.784C560.32 178.048 556.352 182.272 554.752 187.136c-3.2 6.208-3.008 14.208 3.776 20.992L623.36 272.96z"></path>
  <path d="M841.152 457.152c-30.528 0-54.784 24.512-54.784 54.656l0 274.752L237.696 786.56 237.696 237.696l206.016 0c6.656 0 10.752 0 13.248 0C487.68 237.696 512 213.184 512 182.848 512 152.32 487.36 128 456.96 128L183.04 128C153.216 128 128 152.576 128 182.848c0 3.136 0.256 6.272 0.768 9.28C128.256 195.136 128 198.272 128 201.408l0 639.488c0 0.064 0 0.192 0 0.256 0 0.128 0 0.192 0 0.32 0 30.528 24.512 54.784 54.784 54.784l646.976 0c6.592 0 9.728 0 11.712 0 28.736 0 52.928-22.976 54.464-51.968C896 843.264 896 842.304 896 841.344l0-20.352L896 561.408 896 512.128C896 481.792 871.424 457.152 841.152 457.152z"></path>
</svg>

              </i>
            </a>
          
        
      </li><li class="mobile-menu-item">
        
          
          <div class="mobile-menu-parent">
            <span class="mobile-submenu-open"></span>
            <a href="https://yixy.github.io/youzhilane/post/">
              归档
            </a>
          </div>
          <ul class="mobile-submenu-list">
            
              <li>
                <a href="https://yixy.github.io/youzhilane/post/">日期</a>
              </li>
            
              <li>
                <a href="https://yixy.github.io/youzhilane/tags/">标签</a>
              </li>
            
          </ul>
        
      </li>
    

    
  </ul>
</nav>


  
    






  <link rel="stylesheet" href="/youzhilane/lib/photoswipe/photoswipe.min.css" />
  <link rel="stylesheet" href="/youzhilane/lib/photoswipe/default-skin/default-skin.min.css" />




<div class="pswp" tabindex="-1" role="dialog" aria-hidden="true">

<div class="pswp__bg"></div>

<div class="pswp__scroll-wrap">
    
    <div class="pswp__container">
      <div class="pswp__item"></div>
      <div class="pswp__item"></div>
      <div class="pswp__item"></div>
    </div>
    
    <div class="pswp__ui pswp__ui--hidden">
    <div class="pswp__top-bar">
      
      <div class="pswp__counter"></div>
      <button class="pswp__button pswp__button--close" title="Close (Esc)"></button>
      <button class="pswp__button pswp__button--share" title="Share"></button>
      <button class="pswp__button pswp__button--fs" title="Toggle fullscreen"></button>
      <button class="pswp__button pswp__button--zoom" title="Zoom in/out"></button>
      
      
      <div class="pswp__preloader">
        <div class="pswp__preloader__icn">
          <div class="pswp__preloader__cut">
            <div class="pswp__preloader__donut"></div>
          </div>
        </div>
      </div>
    </div>
    <div class="pswp__share-modal pswp__share-modal--hidden pswp__single-tap">
      <div class="pswp__share-tooltip"></div>
    </div>
    <button class="pswp__button pswp__button--arrow--left" title="Previous (arrow left)">
    </button>
    <button class="pswp__button pswp__button--arrow--right" title="Next (arrow right)">
    </button>
    <div class="pswp__caption">
      <div class="pswp__caption__center"></div>
    </div>
    </div>
    </div>
</div>

  

  

  

  <header id="header" class="header container">
    <div class="logo-wrapper">
  <a href="/youzhilane/" class="logo">
    
      友知弄
    
  </a>
</div>

<nav class="site-navbar">
  <ul id="menu" class="menu">
    
    
        <li class="menu-item active">
        
          
          
            <a class="menu-item-link" href="https://yixy.github.io/youzhilane/">主页</a>
          

        

      </li>
    
        <li class="menu-item">
        
          
          
            <a class="menu-item-link" href="https://yixy.github.io/youzhilane/categories/">分类</a>
          

        

      </li>
    
        <li class="menu-item">
        
          
          
            <a class="menu-item-link" href="https://yixy.github.io/youzhilane/booklist/">书单</a>
          

        

      </li>
    
        <li class="menu-item">
        
          
          
            <a class="menu-item-link" href="https://yixy.github.io/youzhilane/about/">关于友知弄</a>
          

        

      </li>
    
        <li class="menu-item">
        
          
          
            <a class="menu-item-link" href="https://github.com/yixy" rel="noopener" target="_blank">
              GitHub
              
              <i class="iconfont">
                <svg class="icon" viewBox="0 0 1024 1024" version="1.1"
  xmlns="http://www.w3.org/2000/svg" xmlns:xlink="http://www.w3.org/1999/xlink"
  width="18" height="18">
  <path d="M623.36 272.96 473.216 423.04C467.2 429.056 467.072 438.656 472.896 444.416c0 0-6.72-6.656 1.6 1.6C496.064 467.648 528.64 500.224 528.64 500.224 534.464 506.048 544 505.856 550.016 499.904l150.08-150.144 67.328 66.432c9.024 8.96 27.456 4.544 30.4-8.96 19.968-92.608 46.656-227.52 46.656-227.52 6.848-34.496-16.192-56.704-49.92-49.92 0 0-134.656 26.816-227.328 46.784C560.32 178.048 556.352 182.272 554.752 187.136c-3.2 6.208-3.008 14.208 3.776 20.992L623.36 272.96z"></path>
  <path d="M841.152 457.152c-30.528 0-54.784 24.512-54.784 54.656l0 274.752L237.696 786.56 237.696 237.696l206.016 0c6.656 0 10.752 0 13.248 0C487.68 237.696 512 213.184 512 182.848 512 152.32 487.36 128 456.96 128L183.04 128C153.216 128 128 152.576 128 182.848c0 3.136 0.256 6.272 0.768 9.28C128.256 195.136 128 198.272 128 201.408l0 639.488c0 0.064 0 0.192 0 0.256 0 0.128 0 0.192 0 0.32 0 30.528 24.512 54.784 54.784 54.784l646.976 0c6.592 0 9.728 0 11.712 0 28.736 0 52.928-22.976 54.464-51.968C896 843.264 896 842.304 896 841.344l0-20.352L896 561.408 896 512.128C896 481.792 871.424 457.152 841.152 457.152z"></path>
</svg>

              </i>
            </a>
          

        

      </li>
    
        <li class="menu-item">
        
          
          <a class="menu-item-link menu-parent" href="https://yixy.github.io/youzhilane/post/">归档</a>
          <ul class="submenu">
            
              <li>
                <a href="https://yixy.github.io/youzhilane/post/">日期</a>
              </li>
            
              <li>
                <a href="https://yixy.github.io/youzhilane/tags/">标签</a>
              </li>
            
          </ul>

        

      </li>
    

    
    

    
  </ul>
</nav>

  </header>

  <div id="mobile-panel">
    <main id="main" class="main bg-llight">
      <div class="content-wrapper">
        <div id="content" class="content container">
          
<section id="posts" class="posts">
  
  
    
  
  
  
    <article class="post bg-white">
  <header class="post-header">
    <h1 class="post-title">
      
      <a class="post-link" href="/youzhilane/post/01%E8%AE%A1%E7%AE%97%E6%9C%BA%E7%A7%91%E5%AD%A6/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84%E4%B8%8E%E7%AE%97%E6%B3%95/11%E7%BA%BF%E6%80%A7%E8%A1%A8%E6%9F%A5%E6%89%BE%E5%88%86%E5%9D%97%E7%B4%A2%E5%BC%95%E6%9F%A5%E6%89%BE/"></a>
    </h1>
    
    <div class="post-meta">
      <time datetime="0001-01-01" class="post-time">
        0001-01-01
      </time>
      
      <span class="more-meta"> 约 6 字 </span>
      <span class="more-meta"> 预计阅读 1 分钟 </span>
      
      
      
    </div>
  </header>
  
  <div class="post-content">
    
    <div class="post-summary">
      静态查找——线性表分块索引查找 将待查找元素分成多个块，先确定待查找记录所在块（顺序或折半），再在块内查找（顺序查找）。
 等概率情况下：ASL=(n/s+s)/2+1，比顺序查找快，比二分查找慢。（s为每块的元素数量） 适用存储结构：顺序表或链表 块间有序，块内无序  线性表分块索引查找性能介于顺序查找和二分查找之间。对于动态查找场景，插入、删除较为容易，无需进行大量元素移动。但需要引入额外的索引存储空间，并对初始索引进行排序计算。
    </div>
    <div class="read-more">
      <a href="/youzhilane/post/01%E8%AE%A1%E7%AE%97%E6%9C%BA%E7%A7%91%E5%AD%A6/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84%E4%B8%8E%E7%AE%97%E6%B3%95/11%E7%BA%BF%E6%80%A7%E8%A1%A8%E6%9F%A5%E6%89%BE%E5%88%86%E5%9D%97%E7%B4%A2%E5%BC%95%E6%9F%A5%E6%89%BE/" class="read-more-link">阅读全文</a>
    </div>
    
  </div>
</article>

  
    <article class="post bg-white">
  <header class="post-header">
    <h1 class="post-title">
      
      <a class="post-link" href="/youzhilane/post/01%E8%AE%A1%E7%AE%97%E6%9C%BA%E7%A7%91%E5%AD%A6/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84%E4%B8%8E%E7%AE%97%E6%B3%95/12%E6%A0%91%E8%A1%A8%E6%9F%A5%E6%89%BE%E4%BA%8C%E5%8F%89%E6%8E%92%E5%BA%8F%E6%A0%91/"></a>
    </h1>
    
    <div class="post-meta">
      <time datetime="0001-01-01" class="post-time">
        0001-01-01
      </time>
      
      <span class="more-meta"> 约 43 字 </span>
      <span class="more-meta"> 预计阅读 1 分钟 </span>
      
      
      
    </div>
  </header>
  
  <div class="post-content">
    
    <div class="post-summary">
       树表查找——二叉排序树 如果希望拥有与折半查找同样的查找效率O(logn)，并且对频繁的插入删除操作不需要大量元素移动，可以使用平衡二叉树。
 时间复杂度最佳情况是 O(log­n)，而最坏情况是 O(n)。 空间复杂度是O(n)，因为有指针。  在介绍平衡二叉树前先介绍二叉排序树。
1. 二叉排序树的定义 二叉排序树（Binary Search Tree，又叫二叉查找树、二叉搜索树），或是空树，或者满足如下性质：
 若其左子树为非空，则左子树上所有结点的值均小于根结点的值 若其右子树为非空，则左子树上所有结点的值均大于等于根结点的值 其左右子树本身又是一棵二叉排序树  按二叉排序树的定义，中序遍历二叉排序树，得到的结果是递增有序的。
2. 二叉排序树的查找  若查找关键字与根结点匹配，则查找成功 若关键字小于根结点，则查其左子树 若关键字大于根结点，则查其右子树 左右子树查找方式类似  注意，BST树比较的关键字次数是此结点的层数，所以其最坏查找次数是树的深度。其平均查找长度与树的形态有关，树的高度越高，平均查找长度越长，最佳情况是 O(log­n)，而最坏情况是 O(n)。
 当 BST 树中的节点以扇形结构散开时，对它的插入、删除和查找操作最优的情况下可以达到亚线性的运行时间 O(log2n)。因为当在 BST 中查找一个节点时，每一步比较操作后都会将节点的数量减少一半。尽管如此，如果拓扑结构呈线性的样子，运行时间就会退减到线性时间 O(n)。因为每一步比较操作后还是需要逐个比较其余的节点。也就是说，在这种情况下，在 BST 中查找节点与在数组（Array）中查找就基本类似了。
 如何提高形态不均衡的二叉排序树的查找效率？
做平衡化处理，即尽量让二叉树的形状均衡。
二叉排序树结点的插入和删除 一个无序序列可以通过构造二叉排序树而变成一个有序序列，构造树的过程就是对无序序列排序的过程。
 插入的结点均为叶子结点，故无需移动其他结点，相当于在有序序列上插入元素而无需移动其他元素。  删除元素应避免树的高度增加。
 叶子结点直接删除 被删除结点只有左子树或者只有右子树，则用其左子树或右子树替换它 被删除结点既有左子树又有右子树：1）以其中序前趋结点值替换之（值替换），然后再删除该前趋结点。某结点的前趋是其左子树中最大的结点；2）以其中序后继结点值替换之（值替换），然后再删除该后继结点。某结点的后继是其右子树中最小的结点；  
    </div>
    <div class="read-more">
      <a href="/youzhilane/post/01%E8%AE%A1%E7%AE%97%E6%9C%BA%E7%A7%91%E5%AD%A6/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84%E4%B8%8E%E7%AE%97%E6%B3%95/12%E6%A0%91%E8%A1%A8%E6%9F%A5%E6%89%BE%E4%BA%8C%E5%8F%89%E6%8E%92%E5%BA%8F%E6%A0%91/" class="read-more-link">阅读全文</a>
    </div>
    
  </div>
</article>

  
    <article class="post bg-white">
  <header class="post-header">
    <h1 class="post-title">
      
      <a class="post-link" href="/youzhilane/post/01%E8%AE%A1%E7%AE%97%E6%9C%BA%E7%A7%91%E5%AD%A6/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84%E4%B8%8E%E7%AE%97%E6%B3%95/13%E6%A0%91%E8%A1%A8%E6%9F%A5%E6%89%BE%E5%B9%B3%E8%A1%A1%E4%BA%8C%E5%8F%89%E6%A0%91avl/"></a>
    </h1>
    
    <div class="post-meta">
      <time datetime="0001-01-01" class="post-time">
        0001-01-01
      </time>
      
      <span class="more-meta"> 约 26 字 </span>
      <span class="more-meta"> 预计阅读 1 分钟 </span>
      
      
      
    </div>
  </header>
  
  <div class="post-content">
    
    <div class="post-summary">
      树表查找——平衡二叉树(AVL) 为了追求使二叉排序树总是保持最佳情况 O(log­2n)，某些情况需要对二叉排序树进行“平衡化”。
 注意，BST树最坏查找次数是树的深度，其平均查找长度与树的形态有关，最佳情况是 O(log­n)，而最坏情况是 O(n)。 AVL在查找、插入和删除在平均和最坏情况下都是O（log n）。空间复杂度是O(n)，因为有指针及平衡因子。  1. 平衡二叉树的定义 平衡二叉树（balanced binary tree），又被称为AVL树（Adelson-Velskii and Landis），一棵平衡二叉树或者是空树，或者是具有下列性质的二叉排序树：
 左子树与右子树的高度之差的绝对值小于等于1 左子树和右子树也是平衡二叉树  平衡因子：为方便起见，给每个结点附加一个数字，给出该结点左子树与右子树的高度差。平衡二叉树上所有结点的平衡因子只能是-1，0，1。
2. 失衡处理 失衡二叉排序树的“平衡化”原则：1）降低树的高度；2）保持二叉树的性质
 A：失衡结点。不止一个失衡结点时，取最小失衡子树（其根结点为失衡结点）进行调整。 B：失衡结点的孩子 C：插入新结点的子树  一个例子。
avl的旋转次数是常数，这个有证明的。但是很多算法书上的伪代码是错误的，它们会一直旋转到root。其实不用的，你可以自己去搜正确的算法，youtube上也有国外大学教授的证明视频
    </div>
    <div class="read-more">
      <a href="/youzhilane/post/01%E8%AE%A1%E7%AE%97%E6%9C%BA%E7%A7%91%E5%AD%A6/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84%E4%B8%8E%E7%AE%97%E6%B3%95/13%E6%A0%91%E8%A1%A8%E6%9F%A5%E6%89%BE%E5%B9%B3%E8%A1%A1%E4%BA%8C%E5%8F%89%E6%A0%91avl/" class="read-more-link">阅读全文</a>
    </div>
    
  </div>
</article>

  
    <article class="post bg-white">
  <header class="post-header">
    <h1 class="post-title">
      
      <a class="post-link" href="/youzhilane/post/01%E8%AE%A1%E7%AE%97%E6%9C%BA%E7%A7%91%E5%AD%A6/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84%E4%B8%8E%E7%AE%97%E6%B3%95/14%E6%A0%91%E8%A1%A8%E6%9F%A5%E6%89%BE%E7%BA%A2%E9%BB%91%E6%A0%91/"></a>
    </h1>
    
    <div class="post-meta">
      <time datetime="0001-01-01" class="post-time">
        0001-01-01
      </time>
      
      <span class="more-meta"> 约 54 字 </span>
      <span class="more-meta"> 预计阅读 1 分钟 </span>
      
      
      
    </div>
  </header>
  
  <div class="post-content">
    
    <div class="post-summary">
      红黑树  红黑树在查找、插入和删除在平均和最坏情况下都是O（log n）。空间复杂度是O(n)，因为有指针及颜色属性。  1. 红黑树的定义 学过二叉查找树的同学都知道，普通的二叉查找树在极端情况下可退化成链表，此时的增删查效率都会比较低下。为了避免这种情况，就出现了一些自平衡的查找树，比如 AVL，红黑树等。这些自平衡的查找树通过定义一些性质，将任意节点的左右子树高度差控制在规定范围内，以达到平衡状态。以红黑树为例，红黑树通过如下的性质定义实现自平衡：
 节点是红色或黑色。 根是黑色。 所有叶子都是黑色（叶子是NIL节点）。 每个红色节点必须有两个黑色子节点。（从每个叶子到根的所有路径上不能有两个连续的红色节点。） 从任一节点到其每个叶子的所有简单路径都包含相同数目的黑色节点（简称黑高）。  当某条路径最短时，这条路径必然都是由黑色节点构成。当某条路径长度最长时，这条路径必然是由红色和黑色节点相间构成（性质4限定了不能出现两个连续的红色节点）。而性质5又限定了从任一节点到其每个叶子节点的所有路径必须包含相同数量的黑色节点。此时，在路径最长的情况下，路径上红色节点数量 = 黑色节点数量。该路径长度为两倍黑色节点数量，也就是最短路径长度的2倍。
插入 红黑树插入新节点后，需要进行调整，以满足红黑树的性质。性质1规定红黑树节点的颜色要么是红色要么是黑色，那么在插入新节点时，这个节点应该是红色还是黑色呢？答案是红色，原因也不难理解。如果插入的节点是黑色，那么这个节点所在路径比其他路径多出一个黑色节点，这个调整起来会比较麻烦（参考红黑树的删除操作，就知道为啥多一个或少一个黑色节点时，调整起来这么麻烦了）。如果插入的节点是红色，此时所有路径上的黑色节点数量不变，仅可能会出现两个连续的红色节点的情况。这种情况下，通过变色和旋转进行调整即可，比之前的简单多了。
情况一：空树插入红色结点，直接变色。
情况二：黑结点下增加红色结点，无需调整。
情况三：需要注意的是 G 被染成红色后，可能会和它的父节点形成连续的红色节点，此时需要递归向上调整。如果G已经是根结点，则直接改变G的颜色为黑色，那么整棵树也是符合红黑树定义的。
情况四：转换成为情况五进行处理。
删除 相较于插入操作，红黑树的删除操作则要更为复杂一些。删除操作首先要确定待删除节点有几个孩子，如果有两个孩子，不能直接删除该节点。而是要先找到该节点的前驱（该节点左子树中最大的节点）或者后继（该节点右子树中最小的节点），然后将前驱或者后继的值复制到要删除的节点中，最后再将前驱或后继删除。由于前驱和后继至多只有一个孩子节点，这样我们就把原来要删除的节点有两个孩子的问题转化为只有一个孩子节点的问题，问题被简化了一些。我们并不关心最终被删除的节点是否是我们开始想要删除的那个节点，只要节点里的值最终被删除就行了，至于树结构如何变化，这个并不重要。
红黑树删除操作的复杂度在于删除节点的颜色，当删除的节点是红色时，直接拿其孩子节点补空位即可。因为删除红色节点，性质5（从任一节点到其每个叶子的所有简单路径都包含相同数目的黑色节点）仍能够被满足。当删除的节点是黑色时，那么所有经过该节点的路径上的黑节点数量少了一个，破坏了性质5。如果该节点的孩子为红色，直接拿孩子节点替换被删除的节点，并将孩子节点染成黑色，即可恢复性质5。但如果孩子节点为黑色，处理起来就要复杂的多。分为6种情况，下面会展开说明。
 情况一：要删除的节点 X 是根节点，且左右孩子节点均为空节点，此时将节点 X 用空节点替换完成删除操作。
 2. AVL与红黑树 红黑树具有良好的效率，它可在 O(logN) 时间内完成查找、增加、删除等操作。因此，红黑树在业界应用很广泛，比如 Java 中的 TreeMap，JDK 1.8 中的 HashMap、C++ STL 中的 map 均是基于红黑树结构实现的。
 AVL树：平衡二叉树，一般是用平衡因子差值决定并通过旋转来实现，左右子树树高差不超过1，那么和红黑树比较它是严格的平衡二叉树，平衡条件非常严格（树高差只有1），只要插入或删除不满足上面的条件就要通过旋转来保持平衡。由于旋转是非常耗费时间的。我们可以推出AVL树适合用于插入删除次数比较少，但查找多的情况。 红黑树：平衡二叉树，通过对任何一条从根到叶子的简单路径上各个节点的颜色进行约束，确保没有一条路径会比其他路径长2倍，因而是近似平衡的。所以相对于严格要求平衡的AVL树来说，它的旋转保持平衡次数较少。用于搜索时，插入删除次数多的情况下我们就用红黑树来取代AVL。（现在部分场景使用跳表来替换红黑树，可搜索“为啥 redis 使用跳表(skiplist)而不是使用 red-black？”）  要较真比较性能的话，如果是有大量查询的场合，AVL可能好一些；不过如果要维护动态树结构的话，红黑树通常更好，因为对平衡性的要求不是那么严格，树结构变化时调整的次数相对较少。
参考 https://segmentfault.com/a/1190000012728513
    </div>
    <div class="read-more">
      <a href="/youzhilane/post/01%E8%AE%A1%E7%AE%97%E6%9C%BA%E7%A7%91%E5%AD%A6/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84%E4%B8%8E%E7%AE%97%E6%B3%95/14%E6%A0%91%E8%A1%A8%E6%9F%A5%E6%89%BE%E7%BA%A2%E9%BB%91%E6%A0%91/" class="read-more-link">阅读全文</a>
    </div>
    
  </div>
</article>

  
    <article class="post bg-white">
  <header class="post-header">
    <h1 class="post-title">
      
      <a class="post-link" href="/youzhilane/post/01%E8%AE%A1%E7%AE%97%E6%9C%BA%E7%A7%91%E5%AD%A6/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84%E4%B8%8E%E7%AE%97%E6%B3%95/15%E6%A0%91%E8%A1%A8%E6%9F%A5%E6%89%BEb%E6%A0%91%E4%B8%8Eb&#43;%E6%A0%91/"></a>
    </h1>
    
    <div class="post-meta">
      <time datetime="0001-01-01" class="post-time">
        0001-01-01
      </time>
      
      <span class="more-meta"> 约 136 字 </span>
      <span class="more-meta"> 预计阅读 1 分钟 </span>
      
      
      
    </div>
  </header>
  
  <div class="post-content">
    
    <div class="post-summary">
      多路查找树——B树与B+树 B/B+ 树就是N叉（N-ary）平衡树了，每个结点可以有更多的孩子，新的值可以插在已有的结点里，而不需要改变树的高度，从而大量减少重新平衡和数据迁移的次数，这非常适合做数据库索引这种需要持久化在磁盘，同时需要大量查询和插入操作的应用。
 B树：B-tree（B-tree树即B树，B即Balanced，平衡的意思）   有的文章里面出现的B-树，即为B树。因为B树的原英文名称为B-tree，而国内很多人喜欢把B-tree译作B-树，其实，这是个非常不好的直译，很容易让人产生误解。如人们可能会以为B-树是一种树，而B树又是一种一种树。而事实上是，B-tree就是指的B树。
  B+树：B+树是B树的变种树，有n棵子树的结点中含有n个关键字，每个关键字不保存数据，只用来索引，数据都保存在叶子结点。  B+树用在磁盘文件组织、数据索引和数据库索引。数据库索引采用B+树的主要原因是B树在提高了磁盘IO性能的同时并没有解决元素遍历的效率低下的问题。正是为了解决这个问题，B+树应运而生。B+树只要遍历叶子节点就可以实现整棵树的遍历。而且在数据库中基于范围的查询是非常频繁的，而B树不支持这样的操作（或者说效率太低）。
 B/B+树时间复杂度：查找、插入和删除在平均和最坏情况下都是O（log n） B/B+树空间复杂度：O(n)，因为有指针（B树还有关键字）  1. B树 2-3树是一种特殊的B树。
M阶B树的定义：
 每一个节点最多有 m 个子节点 每一个非叶子节点（除根节点）最少有 ⌈m/2⌉ 个子节点 如果根节点不是叶子节点，那么它至少有两个子节点 有 k 个子节点的非叶子节点拥有 k − 1 个关键字（即非叶子结点有k个指针和k-1个关键字） 所有的叶子节点都在同一层   m/2的限制一是为了保证存储密度，二是避免树结构退化，保证其在磁盘存储器中的存储优势。正因为 b 树是一个稳定的多叉结构，每一个节点有多个 key 和分支。在磁盘存储器这样的 查找速度慢(硬件条件限制)，以存储块(一个相对较大的块)为单位读取的 硬件结构中，才有了明显的优势。
 2. B树的查找 3. B树的插入 4. B+树 M阶B+树是M阶B树的变种树：
 B+ 树中的非叶子结点不存储关键字数据，只是存储索引；（B 树中的结点存储数据） 通过链表将叶子结点串联在一起，这样可以方便按区间查找；（B树叶子结点没有串联） 一般情况，根结点会被存储在内存中，其他结点存储在磁盘中。  不管是内存中的数据，还是磁盘中的数据，操作系统都是按页（一页大小通常是 4KB，这个值可以通过 getconfig PAGE_SIZE 命令查看）来读取的，一次会读一页的数据。如果要读取的数据量超过一页的大小，就会触发多次 IO 操作。所以，我们在选择 m 大小的时候，要尽量让每个结点的大小等于一个页的大小。读取一个结点，只需要一次磁盘 IO 操作。
    </div>
    <div class="read-more">
      <a href="/youzhilane/post/01%E8%AE%A1%E7%AE%97%E6%9C%BA%E7%A7%91%E5%AD%A6/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84%E4%B8%8E%E7%AE%97%E6%B3%95/15%E6%A0%91%E8%A1%A8%E6%9F%A5%E6%89%BEb%E6%A0%91%E4%B8%8Eb&#43;%E6%A0%91/" class="read-more-link">阅读全文</a>
    </div>
    
  </div>
</article>

  
</section>






  
  
  

  
  

  
  

  
  

  
  

    <nav class="pagination">
      <ul>

      
      
      <li><a href="/youzhilane/">««</a></li>
      

      
      
      <li><a href="/youzhilane/page/10/">«</a></li>
      

      
      

        

        
        

          
          
          

            

          

        
        

        
        

      

        

        
        

          
          
          

            

          

        
        

        
        

      

        

        
        

          
          
          

            

          

        
        

        
        

      

        

        
        

          
          
          

            

          

        
        

        
        

      

        

        
        

          
          
          

            
              
            

          

        
        

        
        
          <li class="">
            <a href="/youzhilane/page/5/">
              5
            </a>
          </li>
        

      

        

        
        

          
          
          

            
              
            

          

        
        

        
        
          <li class="">
            <a href="/youzhilane/page/6/">
              6
            </a>
          </li>
        

      

        

        
        

          
          
          

            
              
            

          

        
        

        
        
          <li class="">
            <a href="/youzhilane/page/7/">
              7
            </a>
          </li>
        

      

        

        
        

          
          
          

            
              
            

          

        
        

        
        
          <li class="">
            <a href="/youzhilane/page/8/">
              8
            </a>
          </li>
        

      

        

        
        

          
          
          

            
              
            

          

        
        

        
        
          <li class="">
            <a href="/youzhilane/page/9/">
              9
            </a>
          </li>
        

      

        

        
        

          
          
          

            
              
            

          

        
        

        
        
          <li class="">
            <a href="/youzhilane/page/10/">
              10
            </a>
          </li>
        

      

        

        
        

          
          
          

            
              
            

          

        
        

        
        
          <li class="active">
            <a href="/youzhilane/page/11/">
              11
            </a>
          </li>
        

      

        

        
        

          
          
          

            
              
            

          

        
        

        
        
          <li class="">
            <a href="/youzhilane/page/12/">
              12
            </a>
          </li>
        

      

        

        
        

          
          
          

            
              
            

          

        
        

        
        
          <li class="">
            <a href="/youzhilane/page/13/">
              13
            </a>
          </li>
        

      

        

        
        

          
          
          

            
              
            

          

        
        

        
        
          <li class="">
            <a href="/youzhilane/page/14/">
              14
            </a>
          </li>
        

      

        

        
        

          
          
          

            
              
            

          

        
        

        
        
          <li class="">
            <a href="/youzhilane/page/15/">
              15
            </a>
          </li>
        

      

        

        
        

          
          
          

            
              
            

          

        
        

        
        
          <li class="">
            <a href="/youzhilane/page/16/">
              16
            </a>
          </li>
        

      

        

        
        

          
          
          

            
              
            

          

        
        

        
        
          <li class="">
            <a href="/youzhilane/page/17/">
              17
            </a>
          </li>
        

      

        

        
        

          
          
          

            

          

        
        

        
        

      

        

        
        

          
          
          

            

          

        
        

        
        

      

      
      
      <li><a href="/youzhilane/page/12/">»</a></li>
      

      
      
      <li><a href="/youzhilane/page/19/">»»</a></li>
      

      </ul>
    </nav>
  





        </div>
      </div>
    </main>

    <footer id="footer" class="footer">
      <div class="icon-links">
  
  
    <a href="mailto:youzhilane01@gmail.com" rel="me noopener" class="iconfont"
      title="email" >
      <svg class="icon" viewBox="0 0 1451 1024" version="1.1"
  xmlns="http://www.w3.org/2000/svg" xmlns:xlink="http://www.w3.org/1999/xlink"
  width="36" height="36">
  <path d="M664.781909 681.472759 0 97.881301C0 3.997201 71.046997 0 71.046997 0L474.477909 0 961.649408 0 1361.641813 0C1361.641813 0 1432.688811 3.997201 1432.688811 97.881301L771.345323 681.472759C771.345323 681.472759 764.482731 685.154773 753.594283 688.65053L753.594283 688.664858C741.602731 693.493018 729.424896 695.068979 718.077952 694.839748 706.731093 695.068979 694.553173 693.493018 682.561621 688.664858L682.561621 688.65053C671.644501 685.140446 664.781909 681.472759 664.781909 681.472759L664.781909 681.472759ZM718.063616 811.603883C693.779541 811.016482 658.879232 802.205449 619.10784 767.734955 542.989056 701.759633 0 212.052267 0 212.052267L0 942.809523C0 942.809523 0 1024 83.726336 1024L682.532949 1024 753.579947 1024 1348.948139 1024C1432.688811 1024 1432.688811 942.809523 1432.688811 942.809523L1432.688811 212.052267C1432.688811 212.052267 893.138176 701.759633 817.019477 767.734955 777.248 802.205449 742.347691 811.03081 718.063616 811.603883L718.063616 811.603883Z"></path>
</svg>

    </a>


<a href="https://yixy.github.io/youzhilane/index.xml" rel="noopener alternate" type="application/rss&#43;xml"
    class="iconfont" title="rss" target="_blank">
    <svg class="icon" viewBox="0 0 1024 1024" version="1.1"
  xmlns="http://www.w3.org/2000/svg" xmlns:xlink="http://www.w3.org/1999/xlink"
  width="30" height="30">
  <path d="M819.157333 1024C819.157333 574.592 449.408 204.8 0 204.8V0c561.706667 0 1024 462.293333 1024 1024h-204.842667zM140.416 743.04a140.8 140.8 0 0 1 140.501333 140.586667A140.928 140.928 0 0 1 140.074667 1024C62.72 1024 0 961.109333 0 883.626667s62.933333-140.544 140.416-140.586667zM678.784 1024h-199.04c0-263.210667-216.533333-479.786667-479.744-479.786667V345.173333c372.352 0 678.784 306.517333 678.784 678.826667z"></path>
</svg>

  </a>
   
</div>

<div class="copyright">
  <span class="power-by">
    Powered by <a class="hexo-link" href="https://gohugo.io">Hugo</a>
  </span>
  <span class="division">|</span>
  <span class="theme-info">
    Theme - <a class="theme-link" href="https://github.com/xianmin/hugo-theme-jane">Jane</a>
  </span>

  <span class="copyright-year">
    &copy;
    2019
    <span class="heart">
      
      <i class="iconfont">
        <svg class="icon" viewBox="0 0 1025 1024" version="1.1"
  xmlns="http://www.w3.org/2000/svg" xmlns:xlink="http://www.w3.org/1999/xlink"
  width="14" height="14">
  <path d="M1000.1 247.9c-15.5-37.3-37.6-70.6-65.7-98.9-54.4-54.8-125.8-85-201-85-85.7 0-166 39-221.4 107.4C456.6 103 376.3 64 290.6 64c-75.1 0-146.5 30.4-201.1 85.6-28.2 28.5-50.4 61.9-65.8 99.3-16 38.8-24 79.9-23.6 122.2 0.7 91.7 40.1 177.2 108.1 234.8 3.1 2.6 6 5.1 8.9 7.8 14.9 13.4 58 52.8 112.6 102.7 93.5 85.5 209.9 191.9 257.5 234.2 7 6.1 15.8 9.5 24.9 9.5 9.2 0 18.1-3.4 24.9-9.5 34.5-30.7 105.8-95.9 181.4-165 74.2-67.8 150.9-138 195.8-178.2 69.5-57.9 109.6-144.4 109.9-237.3 0.1-42.5-8-83.6-24-122.2z"
   fill="#8a8a8a"></path>
</svg>

      </i>
    </span><span class="author">
        yixy
        
      </span></span>

  
  

  
</div>

    </footer>

    <div class="back-to-top" id="back-to-top">
      <i class="iconfont">
        
        <svg class="icon" viewBox="0 0 1024 1024" version="1.1"
  xmlns="http://www.w3.org/2000/svg" xmlns:xlink="http://www.w3.org/1999/xlink"
  width="35" height="35">
  <path d="M510.866688 227.694839 95.449397 629.218702l235.761562 0-2.057869 328.796468 362.40389 0L691.55698 628.188232l241.942331-3.089361L510.866688 227.694839zM63.840492 63.962777l894.052392 0 0 131.813095L63.840492 195.775872 63.840492 63.962777 63.840492 63.962777zM63.840492 63.962777"></path>
</svg>

      </i>
    </div>
  </div>
  
<script type="text/javascript" src="/youzhilane/lib/jquery/jquery-3.2.1.min.js"></script>
  <script type="text/javascript" src="/youzhilane/lib/slideout/slideout-1.0.1.min.js"></script>




<script type="text/javascript" src="/youzhilane/js/main.638251f4230630f0335d8c6748e53a96f94b72670920b60c09a56fdc8bece214.js" integrity="sha256-Y4JR9CMGMPAzXYxnSOU6lvlLcmcJILYMCaVv3Ivs4hQ=" crossorigin="anonymous"></script>












  
    <script type="text/javascript" src="/youzhilane/js/load-photoswipe.js"></script>
    <script type="text/javascript" src="/youzhilane/lib/photoswipe/photoswipe.min.js"></script>
    <script type="text/javascript" src="/youzhilane/lib/photoswipe/photoswipe-ui-default.min.js"></script>
  















</body>
</html>
